package com.lw.leetcode.back.c;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * 679. 24 点游戏
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/20 11:21
 */
public class JudgePoint24 {


    public static void main(String[] args) {
        JudgePoint24 test = new JudgePoint24();

        // true (8-4) * (7-1) = 24
//        int[] arr = {4, 1, 8, 7};

        // false
        int[] arr = {1, 2, 1, 2};

        boolean b = test.judgePoint24(arr);
        System.out.println(b);
    }

    private Stack<Node> values = new Stack<>();
    private Stack<Integer> ops = new Stack<>();

    public boolean judgePoint24(int[] cards) {
        int a = cards[0];
        int b = cards[1];
        int c = cards[2];
        int d = cards[3];
        if (find(new int[]{a, b, c, d})) {
            return true;
        }
        if (find(new int[]{a, b, d, c})) {
            return true;
        }
        if (find(new int[]{a, c, b, d})) {
            return true;
        }
        if (find(new int[]{a, c, d, b})) {
            return true;
        }
        if (find(new int[]{a, d, b, c})) {
            return true;
        }
        if (find(new int[]{a, d, c, b})) {
            return true;
        }
        if (find(new int[]{b, a, c, d})) {
            return true;
        }
        if (find(new int[]{b, a, d, c})) {
            return true;
        }
        if (find(new int[]{b, c, a, d})) {
            return true;
        }
        if (find(new int[]{b, c, d, a})) {
            return true;
        }
        if (find(new int[]{b, d, a, c})) {
            return true;
        }
        if (find(new int[]{b, d, c, a})) {
            return true;
        }
        if (find(new int[]{c, a, b, d})) {
            return true;
        }
        if (find(new int[]{c, a, d, b})) {
            return true;
        }
        if (find(new int[]{c, b, a, d})) {
            return true;
        }
        if (find(new int[]{c, b, d, a})) {
            return true;
        }
        if (find(new int[]{c, d, a, b})) {
            return true;
        }
        if (find(new int[]{c, d, b, a})) {
            return true;
        }
        if (find(new int[]{d, a, b, c})) {
            return true;
        }
        if (find(new int[]{d, a, c, b})) {
            return true;
        }
        if (find(new int[]{d, b, a, c})) {
            return true;
        }
        if (find(new int[]{d, b, c, a})) {
            return true;
        }
        if (find(new int[]{d, c, a, b})) {
            return true;
        }
        if (find(new int[]{d, c, b, a})) {
            return true;
        }
        return false;
    }

    public boolean find(int[] cards) {
        Node a;
        Node b;
        Node c;
        Node d;
        Node addOp = new Node(-1, 0, -1);
        Node subOp = new Node(-2, 0, -1);
        Node mulOp = new Node(-3, 0, -1);
        Node divOp = new Node(-4, 0, -1);
        Node l = new Node(-5, 0, -1);
        Node r = new Node(-6, 0, -1);
        Node[] opss = new Node[]{addOp, subOp, mulOp, divOp};
        Node one;
        Node two;
        Node three;
        for (int i = 0; i < 4; i++) {
            one = opss[i];
            for (int j = 0; j < 4; j++) {
                two = opss[j];
                for (int k = 0; k < 4; k++) {
                    three = opss[k];
                    a = new Node(cards[0], 1, 0);
                    b = new Node(cards[1], 1, 0);
                    c = new Node(cards[2], 1, 0);
                    d = new Node(cards[3], 1, 0);
                    if (getSum(new Node[]{a, one, b, two, c, three, d})) {
                        return true;
                    }
                    a = new Node(cards[0], 1, 0);
                    b = new Node(cards[1], 1, 0);
                    c = new Node(cards[2], 1, 0);
                    d = new Node(cards[3], 1, 0);
                    if (getSum(new Node[]{l, a, one, b, r, two, c, three, d})) {
                        return true;
                    }
                    a = new Node(cards[0], 1, 0);
                    b = new Node(cards[1], 1, 0);
                    c = new Node(cards[2], 1, 0);
                    d = new Node(cards[3], 1, 0);
                    if (getSum(new Node[]{l, a, one, b, two, c, r, three, d})) {
                        return true;
                    }
                    a = new Node(cards[0], 1, 0);
                    b = new Node(cards[1], 1, 0);
                    c = new Node(cards[2], 1, 0);
                    d = new Node(cards[3], 1, 0);
                    if (getSum(new Node[]{a, one, l, b, two, c, r, three, d})) {
                        return true;
                    }
                    a = new Node(cards[0], 1, 0);
                    b = new Node(cards[1], 1, 0);
                    c = new Node(cards[2], 1, 0);
                    d = new Node(cards[3], 1, 0);
                    if (getSum(new Node[]{a, one, l, b, two, c, three, d, r})) {
                        return true;
                    }
                    a = new Node(cards[0], 1, 0);
                    b = new Node(cards[1], 1, 0);
                    c = new Node(cards[2], 1, 0);
                    d = new Node(cards[3], 1, 0);
                    if (getSum(new Node[]{a, one, b, two, l, c, three, d, r})) {
                        return true;
                    }
                    a = new Node(cards[0], 1, 0);
                    b = new Node(cards[1], 1, 0);
                    c = new Node(cards[2], 1, 0);
                    d = new Node(cards[3], 1, 0);
                    if (getSum(new Node[]{l, a, one, b, r, two, l, c, three, d, r})) {
                        return true;
                    }
                    a = new Node(cards[0], 1, 0);
                    b = new Node(cards[1], 1, 0);
                    c = new Node(cards[2], 1, 0);
                    d = new Node(cards[3], 1, 0);
                    if (getSum(new Node[]{l, l, a, one, b, r, two, c, r, three, d})) {
                        return true;
                    }
                    a = new Node(cards[0], 1, 0);
                    b = new Node(cards[1], 1, 0);
                    c = new Node(cards[2], 1, 0);
                    d = new Node(cards[3], 1, 0);
                    if (getSum(new Node[]{l, a, one, l, b, two, c, r, r, three, d})) {
                        return true;
                    }
                    a = new Node(cards[0], 1, 0);
                    b = new Node(cards[1], 1, 0);
                    c = new Node(cards[2], 1, 0);
                    d = new Node(cards[3], 1, 0);
                    if (getSum(new Node[]{a, one, l, l, b, two, c, r, three, d, r})) {
                        return true;
                    }
                    a = new Node(cards[0], 1, 0);
                    b = new Node(cards[1], 1, 0);
                    c = new Node(cards[2], 1, 0);
                    d = new Node(cards[3], 1, 0);
                    if (getSum(new Node[]{a, one, l, b, two, l, c, three, d, r, r})) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    // + -1,
    // - -2,
    // * -3,
    // / -4,
    // ( -5,
    // ) -6
    private boolean getSum(Node[] arr) {
        values.clear();
        ops.clear();
        for (int i = 0; i < arr.length; i++) {
            Node node = arr[i];
            if (node.f < 0) {
                if (node.a == -6) {
                    Node item = values.pop();
                    while (ops.pop() != -5) {
                        item.add(values.pop());
                    }
                    arr[i] = item;
                    i--;
                } else {
                    ops.add(node.a);
                }
            } else {
                if (ops.isEmpty() || ops.peek() == -5 || ops.peek() == -1) {
                    values.add(node);
                    continue;
                }
                int peek = ops.pop();
                if (peek == -2) {
                    node.a = -node.a;
                    values.add(node);
                    ops.add(-1);
                    continue;
                }
                Node t = values.peek();
                if (peek == -3) {
                    t.mul(node);
                } else {
                    if (!t.div(node)) {
                        return false;
                    }
                }
            }
        }
        Node v = values.pop();
        while (!values.isEmpty()) {
            v.add(values.pop());
        }
        return v.b * 24 == v.a;
    }

    private class Node {
        private int a;
        private int b;
        private int f;

        private void add(Node node) {
            if (node.b == this.b) {
                this.a += node.a;
                return;
            }
            int b1 = node.b * this.b;
            int a1 = this.a * node.b + this.b * node.a;
            int gcd = gcd(a1, b1);
            this.a = a1 / gcd;
            this.b = b1 / gcd;
        }

        private void mul(Node node) {
            int b1 = node.b * this.b;
            int a1 = this.a * node.a;
            int gcd = gcd(a1, b1);
            this.a = a1 / gcd;
            this.b = b1 / gcd;
        }

        private boolean div(Node node) {
            if (node.a == 0) {
                return false;
            }
            int t = node.b;
            node.b = node.a;
            node.a = t;
            mul(node);
            return true;
        }

        public Node(int a, int b, int f) {
            this.a = a;
            this.b = b;
            this.f = f;
        }
    }

    private int gcd(int r, int e) {
        if (e == 0) {
            return r;
        }
        return gcd(e, r % e);
    }

}
